The present invention relates to a method and apparatus for modular inversion which is carried out for information security, for example, in digital cryptosystems and digital authentication systems which use encryption key generation, digital signature, and blind signature schemes, and elliptic cryptosystem and so forth. The invention also pertains to a recording medium with the modular inversion method recorded thereon.
In the field of information security it is well-known that the calculation of modular inverse over a prime finite field GF(p) (where p is a prime) or residue class ring Z/NZ (Z is a group of integers and N is a positive integer) takes a wide variety of forms, some of which will be described below.
(a) Generation of sum (x3, y3) of two points (x1, y1) and (x2, y3) on an elliptic curve E/GF(p):λ=(y2−y1)/(x2−x1)mod p  (a-1)x3=λ2−x1−x2 mod p  (a-2)y3λ(x1−x3)−y1 mod p  (a-3)
(b) Part of signature generation of digital signature system ESIGN:y=w/(kxk−1)mod p  (b-1)                where x is an integer 1≦x≦pq−1, w is an integer in the range of 0≦w≦p−1, kεZ, and p and q are primes.        
(c) Blind signature generation of digital signature system RSA:s′=(rem)d mod N  (c-1)s=s′/r mod N  (c-2)                where r and m are integers 0≦r and m≦N−1, and e and d are integers 1≦e and d≦φ(N)−1, respectively.        
The above examples use modular multiplications and modular inversions. The Montgomery method has been proposed to efficiently calculate modular residues. Listed below are definitions of some types of modular inversion that suit the Montgomery method.Normal inversion i1(X)=X−1 mod N Kaliski inversion i2(X)=X−1B mod N Montgomery inversion i3(X)=X−1B2 mod N where B=2n, n is the number of bits of N, N<B<2N and Xε=Z/NZ The modular inversion mentioned herein includes any types of modular inversion as well as the above. Replacing the N with a prime p, the above-mentioned inverse will be an inverse over GF(p). The following description will be given only of Z/NZ
Conventionally, for inputs X and N where X is equal to or greater than zero and smaller than N, a modular inverse of X over Z/NZ is calculated, for example, using an extended binary GCD method (extended binary Greatest Common Divisor method, an algorithm for producing X−12k mod N and k, the former being expressed by bgcd(X, N)) The following example will be described in connection with the calculation of a Montgomery inverse.
Method 1:
Step 1: Calculate S and k byS=bgcd(X,N)=X−12k mod N  (1)where n≦k≦2n.
Step 2: Calculate a modular inverse R byR=S22n−k mod N=N−122n mod N  (2)
Step 1 is a process of executing the extended binary GCD algorithm for the inputs X and N. Since 2n−k>0, Step 2 is to calculate multiplication by power of 2.
Incidentally, when d<0,
(a) Multiplication by power of 2: Xd mod N
(b) Division by power of 2: x2−d mod N
the calculation (b) can be done faster than (a).
The calculation (b) can also be used to obtain a Montgomery inverse by the method 2 shown below:
Method 2:Step 1:Y=X2−n mod N  (3)Step 2:S=bgcd(Y,N)(=X−12n+k mod N)  (4)Step 3:R=S2−(k−n)mod N(=X−122n mod N)  (5)
Since k−n≧0, Step 3 performs a division by power of 2.
If the multiplication (a) and the division (b) consumes the same amount of time, then Method 1 involving the smaller number of steps enables the calculation to be made in a shorter time than in the case of using Method 2. In practice, however, since the division (b) can be conducted in a shorter time, it is presumed that the modular inversion by Method 2 may sometimes be processed in a shorter time.
Assuming that N is too large a value to calculate or process by an ordinary computer or processor at a time, the amounts of time for the calculations (a) and (b) increase as d becomes larger.
For example, in the case of using a method in which elementary operations are                (a) Multiplication by 2: X2 mod N        (b) Division by 2: X2−1 mod Nand the calculation (a) is carried out d times as the calculation (a), the time for calculation (a) is d times longer than the time for calculation (a). Similarly, the time for calculation (b) is d times longer than that for calculation (b). The operations corresponding to calculations (a) and (b) will hereinafter be referred to as an elementary operation.        
Method 2 conducts division by power of 2 instead of performing multiplication by power of 2 in Method 1, but needs to perform the elementary operation a larger number of times than does Method 1.
For example, when k=1.41n (It has been experimentally demonstrated that k and n bear this relation on average.) Method 1 performs the Bgcd algorithm, and besides, the elementary operation 0.59 times in Step 2. On the other hand, Method 2 performs the elementary operation n times in Step 1 and 0.41 n times in Step 3 in addition to the Bgcd algorithm, and hence it conducts the elementary calculation a total of 1.41 n times. Accordingly, there is no possibility of Method 2 becoming faster than Method 1 unless the division by power of 2 is considerably faster than the multiplication by power of 2 (more than 2.3 times faster in the above example). Conversely, even if means for speeding up the multiplication by power 2, though not feasible at present, is available, no speedups are possible if only the division by power of 2 occurs.